O(N^2) Sort Algorithms

Sort A list by using “insrert” method

def insert_sort(A):
    N = len(A)
    for top in range(1, N):               # top - current element
        k = top                           # k - current position
        while k > 0 and A[k-1] > A[k]:    # order in "and" is critical
            A[k], A[k-1] = A[k-1], A[k]
            k -= 1

Sort A list by using “choise” method

def choise_sort(A):
    N = len(A)
    for pos in range(0, N - 1):
        for k in range(pos + 1, N):
            if A[k] < A[pos]:
                A[k], A[pos] = A[pos], A[k]

Sort A list by using “bubble” method

def bubble_sort(A):
    N = len(A)
    for bypass in range(1, N):
        for k in range(0, N - bypass):
            if A[k] > A[k+1]:
                A[k], A[k+1] = A[k+1], A[k]

Sort A list by using “selection” method

def _find_smallest(A, idx):
    val = A[idx]
    for i in range(idx, len(A)):
        if A[i] < val:
            val, idx = A[i], i
    return idx

def selection_sort(A):
    for i in range(len(A)):
        smallest_idx = _find_smallest(A, i)   # starting from current i
        if i != smallest_idx:
            A[i], A[smallest_idx] = A[smallest_idx], A[i]

# test

def test_sort(sort_algorithm):

    print("Testing: ", sort_algorithm.__doc__)

    print("testcase #1: ", end="")
    A = [4, 2, 5, 1, 3]
    A_sorted = [1, 2, 3, 4, 5]
    sort_algorithm(A)
    print("Ok" if A == A_sorted else "Fail")

    print("testcase #2: ", end="")
    A = list(range(10, 20)) + list(range(0, 10))
    A_sorted = list(range(20))
    sort_algorithm(A)
    print("Ok" if A == A_sorted else "Fail")

    print("testcase #3: ", end="")
    A = [4, 2, 4, 2, 1]
    A_sorted = [1, 2, 2, 4, 4]
    sort_algorithm(A)
    print("Ok" if A == A_sorted else "Fail")

    print("testcase #4: ", end="")
    A = [1, 23, 12, 9, 30, 2, 50]
    A_sorted = [1, 2, 9, 12, 23, 30, 50]
    sort_algorithm(A)
    print("Ok" if A == A_sorted else "Fail")

if __name__ == "__main__":
    test_sort(insert_sort)
    test_sort(choise_sort)
    test_sort(bubble_sort)
    test_sort(selection_sort)